package com.leetcode.LC_MED;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class LC33 {
    public int search(int[] nums, int target) {
        int a = 0, b = nums.length - 1;

        while (a <= b) {
            int mid = a + (b - a) / 2;
            if (nums[mid] == target) {
                return mid;
                //4,5,6,7,8,9,0,1,2
            } else if (nums[mid] > nums[a]) {//前半段有序
                if (nums[mid] > target && target >= nums[a]) {
                    b = mid-1;
                } else {
                    a = mid+1;
                }
            } else {//后半段有序
                if (nums[mid] < target && target <= nums[b]) {
                    a = mid+1;
                } else {
                    b = mid-1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        LC33 lc33 = new LC33();
        int[] ints = {4, 5, 6, 7, 0, 1, 2};
        System.out.println(lc33.search(ints, 4));
        ArrayList<Integer> integers = new ArrayList<>();
        integers.sort(Comparator.comparingInt(o -> o));
    }
}
